package com.company.algo.huawei;

public class GameWinner {
    public static void main(String[] args) {
//        int[] input= {1,3,2,4,6,5,7,2};//1-3,2-4,6-5,7-2 -淘汰小的-> 3-4,6-7 -淘汰大的-> 3-6 -淘汰小的->6
        int[] input= {7,3,2,4,2,5,7,2};//7-3,2-4,2-5,7-2 -淘汰小的-> 7-4,5-7 -淘汰大的-> 4-5 -淘汰小的->5
        boolean flag = true;
        int counter = 1;

        while (counter < input.length){
            for (int i = 0; i < input.length; i++) {
                int a = getValidIdx(i,input);
                int b = i = getValidIdx(a+1,input);
                if (a == b) continue;
                if (flag){  //淘汰小的
                    input[input[a]<input[b]?a:b] = -1;
                }else {     //淘汰大的
                    input[input[a]>input[b]?a:b] = -1;
                }
                counter++;
            }
            flag = !flag;
        }

        for (int x : input) {
            if (x!=-1) System.out.println(x);
        }
    }

    public static int getValidIdx(int i,int[] input){
        if (i >= input.length - 1) return input.length-1;
        while (i <input.length-2 && input[i]==-1) i = i+1;
        return i;
    }
}
